//
//  10.矩形覆盖.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？比如n=3时，2*3的矩形块有3种覆盖方法
 思路：我们先把2x8的覆盖⽅法记为f(8)。⽤第⼀个1x2⼩矩阵覆盖⼤矩形的最左边时有两个选择，竖着放或者横着放。当竖着放的时候，右边还剩下2x7的区 域，这种情况下的覆盖⽅法记为f(7)。接下来考虑横着放的情况。当1x2的⼩矩形横着放在左上⻆的时候，左下⻆和横着放⼀个1x2的⼩矩形，⽽在右边还剩 下2x6的区域，这种情况下的覆盖⽅法记为f(6)。因此f(8)=f(7)+f(6)。此时我们可以看出，这仍然是斐波那契数列。
 */
func offer_10() {
    print(Solution().rectCover(10))
}

fileprivate class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return int整型
     */
    func rectCover(_ number: Int) -> Int {
        // write code here
        if number < 3 {
            return number
        }
        var first = 1
        var second = 2
        var count = 0
        for _ in 3...number {
            count = first + second
            first = second
            second = count
        }
        return count
    }
}
